package algorithm;

public class MorrisIn {

    public static void morrisIn(TreeNode head) {
        if (head == null) {
            return;
        }

        TreeNode cur = head;
        TreeNode mostRight = null;
        while (cur != null) {
            mostRight = cur.left;

            // 有左孩子
            if (mostRight != null) {
                // 拿到子树的最右节点
                while(mostRight.right != null && cur != mostRight.right) {
                    mostRight = mostRight.right;
                }

                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    // cur == mostRight.right 的情况
                    mostRight.right = null;
                }
            }
            //System.out.println(cur.val + " ");
            cur = cur.right;
        }
        //System.out.println();
    }
    public static void main(String[] args) {

    }
}
